/*
 ============================================================================
 Name        : TournamentAlgo.c
 Author      :
 Version     :
 Copyright   : Your copyright notice
 Description : Implementation of Tournament algorithm.
 ============================================================================
 */
//////////////////////////////////////////////////////////////////////////
//CAS
//////////////////////////////////////////////////////////////////////////
#if defined(__linux__) || defined(__linux) || defined(__gnu_linux__)
	//////////////////////////////////////////////////////////////////////////
	//types
	//////////////////////////////////////////////////////////////////////////
	typedef unsigned char      _u8;
	typedef unsigned short     _u16;
	typedef unsigned int       _u32;
	typedef unsigned long long _u64;
	typedef unsigned long long tick_t;
	typedef _u32               ptr_t;
	#define CAS32(_a,_o,_n)         __sync_val_compare_and_swap ((_u32*)_a,(_u32)_o,(_u32)_n)
	#define MB()  __sync_synchronize()
	#define RDTICK() \
        ({ tick_t __t; __asm__ __volatile__ ("rdtsc" : "=A" (__t)); __t; })
#elif defined(__sun__) || defined(__sun) || defined(sun)
	#include"sparc_defs_cc_TV.h"
#endif


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <math.h>
#include <time.h>

#define true             1
#define false            0
#define  FREE_NODE       -1
#define FREE_LOCK        1024

typedef struct sharedData
{
	volatile char**         b;
	volatile short**        turn;
	volatile tick_t         startTime;
	volatile tick_t         finishTime;
	volatile unsigned long int       countVisitInCS;
	volatile unsigned int   testMutualExclusion;
	volatile unsigned int   startClock;
	unsigned int            numEnters;
	unsigned short int      maxThreadNum;
	unsigned short int      toursize;
	volatile short int      flagStartClock;
	volatile short int      flag;

}sharedData;

typedef struct thData
{
	sharedData*    sData;
	long int       counter;
	short int      id;
        char           padding[54];
}thData;

pthread_barrier_t bar;

void clearVar(sharedData* pSharedData)                     /* Free memory */
{
	int i;

	pthread_barrier_destroy(&bar);

	if((pSharedData->turn != NULL)&&(pSharedData->b != NULL))
	{
		for(i=0; i<pSharedData->toursize; i++)
		{
			free((void*)pSharedData->b[i]);

			pSharedData->b[i] = NULL;

			free((void*)pSharedData->turn[i]);

			pSharedData->turn[i] = NULL;
		}

		free(pSharedData->b);

		pSharedData->b = NULL;

		free(pSharedData->turn);

		pSharedData->turn = NULL;
	}

	free(pSharedData);

	pSharedData = NULL;
}

void test(thData* data)                                    // Test that only one process exist in critical section
{
	if(CAS32(&data->sData->testMutualExclusion, FREE_LOCK, data->id) != FREE_LOCK)
	{
		printf("\nError, mutual exclusion fail.\n");
	}

	CAS32(&data->sData->testMutualExclusion, data->id, FREE_LOCK);
}


void *threadRunTournament(void* ptr)                       // Tournament algorithm
{
	int id, level, node, j;
	/************** Initialized setting ******************/

	thData*              pThData = (thData*)ptr;

	sharedData*          sData = pThData->sData;

	volatile char**     b     = sData->b;

	volatile short**     turn  = sData->turn;

	/************** All thread start to run together ******************/
//	pthread_barrier_wait(&bar);                        // Marked as comment when single process run alone

	if (CAS32(&sData->startClock, FREE_LOCK, 0) == FREE_LOCK) //Start time measuring
	{
		sData->startTime = RDTICK();
		sData->flagStartClock = false;
//		MB();
	}

	while(sData->flagStartClock)
	{}

	while(sData->flag)
	{

	/************** Entry code ****************************************/

	node       = pThData->id;

	/*up hill*/
	for(level=0; level < sData->toursize; level++  )
	{
		id = node & 1;

		node >>= 1;

		b[level][node*2 +id] = true;

		turn[level][node]=id;

//		MB();

		while(b[level][node*2 + 1 -id]==true && turn[level][node] == id)
		{}

	}


		/************** Critical section *******************************/

		 sData->countVisitInCS++;

//                test(pThData);

		 pThData->counter++;

		 if(sData->countVisitInCS == sData->numEnters)
		 {
			{
				 //Stop time measuring
				 sData->finishTime= RDTICK();
				 sData->flag = 0;
//				 MB();
			}
		 }


		/************** Exit code **************************************/

		 /* down hill */

		for(level = sData->toursize - 1 ; level>=0; level--  )
		{

			node = pThData->id>>level;

			b[level][node] = false;

//	        	MB();
		}

	}

//	printf("%ld ",pThData->counter);

	if (pThData->id< sData->maxThreadNum -1)
	{
		pthread_exit(NULL);
	}

    return NULL;
}

void *threadWrite(void* ptr)                               //creating RMR's
{
	int id, level, node;
	/************** Initialized setting ******************/

	thData*              pThData = (thData*)ptr;

	sharedData*          sData = pThData->sData;

	volatile char**     b     = sData->b;

	volatile short**     turn  = sData->turn;

	while(sData->flag)
	{

		node       = sData->maxThreadNum -2;

		/*up hill*/
		for(level=0; level < sData->toursize; level++  )
		{
			id = node & 1;

			node >>= 1;

			b[level][node*2 +id] = false;

		}
	}


	if (pThData->id< sData->maxThreadNum -1)
	{
		pthread_exit(NULL);
	}

    return NULL;
}

sharedData* initalizeVar(int argc,char* argv[])            // Memory allocating and Initialize Data structures
{
	int i,j, levelSize;

	size_t shortSize = sizeof(short);

	sharedData* pSharedData = (sharedData*)malloc(sizeof(sharedData));

	pSharedData->maxThreadNum = 0;

	pSharedData->numEnters    = 0;

	pSharedData->b            = NULL;

	pSharedData->turn         = NULL;

	if ( argc == 4 ) {

		pSharedData->maxThreadNum = atoi(argv[2]);

		pSharedData->numEnters    = atoi(argv[3]);


		if (pSharedData->maxThreadNum < 1)
		{
			 printf("0 processes\n");
			 return NULL;
		}

		freopen (*++argv,"a",stdout);

		printf("Tournament ");

		pSharedData->toursize = log2(pSharedData->maxThreadNum);

		pSharedData->b = (volatile char**)malloc(pSharedData->toursize * sizeof(char*));

		pSharedData->turn = (volatile short**)malloc(pSharedData->toursize * sizeof(short*));

		levelSize = pSharedData->maxThreadNum;

		for(i=0; i<pSharedData->toursize; i++)
		{
			pSharedData->b[i] = (char*)malloc(levelSize * sizeof(char));

			for(j=0; j<levelSize; j++)
			{
				pSharedData->b[i][j] = FREE_NODE;
			}

			levelSize = levelSize >> 1;

			pSharedData->turn[i] = (short*)malloc(levelSize * shortSize);


			for(j=0; j<levelSize; j++)
			{
				pSharedData->turn[i][j] = 0;
			}
		}



	}

	pthread_barrier_init(&bar, NULL, pSharedData->maxThreadNum);

	pSharedData->testMutualExclusion = FREE_LOCK;

	pSharedData->countVisitInCS = 0;

	pSharedData->flag = 1;

	pSharedData->flagStartClock = 1;

	pSharedData->startClock = FREE_LOCK;

	return pSharedData;
}


int main(int argc, char *argv[]) {

	int i;

	tick_t time;

	sharedData* pSharedData = initalizeVar(argc, argv);

	pthread_t*  threads     = (pthread_t*) malloc((pSharedData->maxThreadNum -1)* sizeof(pthread_t));

	thData*     tData       = (thData*)malloc(pSharedData->maxThreadNum * sizeof(thData));


	for(i=0; i<pSharedData->maxThreadNum ; i++)
	{
		tData[i].id     = i;
                tData[i].counter   = 0;                		
                tData[i].sData  = pSharedData;
//		if(i <pSharedData->maxThreadNum - 1)       // Marked as comments when single process run alone
//		{
//			pthread_create(&threads[i], NULL, threadRunTournament, &tData[i]);
//		}
	}

//	pthread_create(&threads[0], NULL, threadWrite, &tData[0]); // Create process who cause RMRS in single process run

	threadRunTournament(&tData[pSharedData->maxThreadNum - 1]);

//	pthread_join(threads[0], NULL);                            // Wait for process who cause RMR's to finish.

//	for(i=0; i<pSharedData->maxThreadNum - 1; i++)     // Marked as comments when single process run alone
//	{
//		pthread_join(threads[i] , NULL);
//	}


	time = pSharedData->finishTime - pSharedData->startTime;

	printf("%d %d %llu\n", pSharedData->maxThreadNum, pSharedData->numEnters,time);

	clearVar(pSharedData);

	free(threads);

	free(tData);

	fclose(stdout);


	return EXIT_SUCCESS;
}


